class Solution {
public:
    bool row[9][10] = {false};
    bool col[9][10] = {false};
    bool b[3][3][10] = {false};
    bool dfs(vector<vector<char>>& board) {
        int i, j;
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    break;
            }
            if (board[i][j] == '.')
                break;
        }
        if(i == 9 && j == 9) return true;
        for (int k = 1; k < 10; k++) {
            if (!row[i][k] && !col[j][k] && !b[i/3][j/3][k]) {
                board[i][j] = k + '0';
                row[i][k] = col[j][k] = b[i/3][j/3][k] = true;
                if(dfs(board) == true) return true;
                board[i][j] = '.';
                row[i][k] = col[j][k] = b[i/3][j/3][k] = false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = b[i/3][j/3][num] = true;
                }
            }
        }
        dfs(board);
    }
};